
#include <vector>
using namespace std;

class Solution {
public:
    int waysToStep(int n) {

        //处理越界问题
        if(1 == n || 2 == n)
        return n;

        vector<int> dp(n+1);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        const int MOD = 1e9 + 7;
        for(int i = 4;i<=n;++i)
        {
            dp[i] = ((dp[i-1] + dp[i-2])%MOD + dp[i-3]%MOD)%MOD;
        }
        return dp[n];
    }
};